#define _CRT_SECURE_NO_WARNINGS 1
//https://www.luogu.com.cn/training/9349
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;


//int main()
//{
//	double a, b = 0.0;
//	cin >> a >> b;
//	int ret = (a + b / 10) / 1.9;
//	cout << ret << endl;
//	return 0;
//}


//int main()
//{
//	int n;
//	cin >> n;
//	int a, b;
//	int minc = 1e9;
//	int i = 3;
//	while (i)
//	{
//		cin >> a >> b;
//		if (a % b == 0)
//		{
//			minc = min(minc, n / a * b);
//		}
//		else
//		{
//			minc = min(minc, (n / a + 1) * b);
//		}
//		--i;
//	}
//	cout << minc << endl;
//	return 0;
//}


//int main()
//{
//	int year = 12;
//	int cost, set, ret, last = 0;
//	for (int i = 1; i <= year; i++)
//	{
//		cin >> cost;
//		set = last + 300 - cost;
//		if (last < 0)
//		{
//			cout << '-' << endl;
//			return 0;
//		}
//		while (set >= 100)
//		{
//			set -= 100;
//			ret += 100;
//		}
//	}
//	if (ret >= 0)
//	{
//		ret = ret * 1.2 + set;
//	}
//	cout << ret << endl;
//	return 0;
//}

//int main()
//{
//	int week = 7;
//	int a, b;
//	int maxd = 0;
//	for (int i = 1; i <= 7; i++)
//	{
//		cin >> a >> b;
//		maxd = max(maxd, a + b);
//		if (a + b > 8 )
//		{
//			cout << i;
//			return 0;
//		}
//	}
//	cout << 0;
//	return 0;
//}


//int main()
//{
//	int k;
//	double sum = 0.0;
//	double n = 0;
//	cin >> k;
//	while(1)
//	{
//		++n;
//		sum = sum + 1/n;
//		if (sum > k)
//		{
//			cout << n;
//			return 0;
//		}
//	}
//	return 0;
//}



//int main()
//{
//	int n, x, c = 0, count = 0;
//	cin >> n >> x;
//	for (int i = 1; i <= n; ++i)
//	{
//		int tmp = i;
//		while (tmp != 0)
//		{
//			c = tmp % 10;
//			tmp /= 10;
//			if (c == x)
//			{
//				++count;
//			}
//		}
//
//	}
//	cout << count << endl;
//	return 0;
//}


//int main()
//{
//	int n, k=1;
//	while (n > k)
//	{
//		n -= k;
//		++k;
//	}
//	if (k % 2 == 0)
//	{
//		cout << n << '/' << (k + 1 - n) << endl;
//	}
//	else
//	{
//		cout << (k + 1 - n) << '/' << n << endl;
//	}
//	return 0;
//}


//int main()
//{
//	int n;
//	int sum = 0;
//	cin >> n;
//
//	while (n != 0)
//	{
//		int tmp = n % 10;
//		n /= 10;
//		sum = sum * 10 + tmp;
//	}
//	cout << sum;
//	return 0;
//}


//int main()
//{
//	int n = 10;
//	int a[10];
//	int count = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//	}
//	int hight = 30, h;
//	cin >> h;
//	for (int i = 1; i <= n; i++)
//	{
//		if (h + hight >= a[i])
//		{
//			++count;
//		}
//	}
//	cout << count;
//	return 0;
//}


//int main()
//{
//	int l, m;
//	cin >> l >> m;
//	int a[100], b[100];
//	int count = l;
//	for (int i = 0; i < m; i++)
//	{
//		cin >> a[i] >> b[i];
//	}
//	for (int i = 0; i < m; i++)
//	{
//		count = count - (b[i] - a[i] + 1);
//	}
//	cout << count;
//	return 0;
//}

//int main()
//{
//	int n = 1, count = 0;
//	int a[100],i = 0;
//	while (n)
//	{
//		cin >> n;
//		a[i] = n;
//		++i;
//		++count;
//	}
//	for (int i = 0; i < count; i++)
//	{
//		cout << a[i] << " ";
//	}
//	return 0;
//}



//int main()
//{
//	int n, count = 0;
//	int flag[20010] = { 0 };
//	cin >> n;
//	int a[110];
//	for (int i = 0; i < n; i++)
//	{
//		cin >> a[i];
//		flag[a[i]] = 1;
//	}
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = i + 1; j < n; j++)
//		{
//			if (flag[a[i] + a[j]])
//			{
//				++count;
//				flag[a[i] + a[j]] = 0;
//			}
//		}
//	}
//	cout << count << endl;
//	return 0;
//}



//#include<iostream>
//#include<bitset>
//using namespace std;
// 
//bitset<1010> a[1010];
//int main()
//{
//	int n, m, k, x;
//	cin >> n >> m >> k;
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			cin >> x;
//			a[x][j] = 1;
//		}
//	}
//	for (int i = 1; i <= k; i++)
//	{
//		cout << a[i].count() << " ";
//	}
//	return 0;
//}